package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 386. 字典序排数
 * Tries(前缀树)
 *
 * @author fy
 * @date 2022/4/18 10:52
 */
public class Solution386_2 {

    public List<Integer> lexicalOrder(int n) {
        Tries r = new Tries();
        r.insert(r.root, n, 0);
        return r.ls;
    }

    public class Tries {
        Node root = new Node();
        List<Integer> ls = new ArrayList<>();

        class Node {
            Node[] values = new Node[10];
            int curr;
        }

        public void insert(Node node, int target, int preval) {
            for (int i = 0; i < 10; i++) {
                if (node.values[i] == null) {
                    node.values[i] = new Node();
                    node.values[i].curr = preval * 10 + i;
                }
                if (node.values[i].curr > target) {
                    return;
                }
                if (node.values[i].curr != 0) {
                    ls.add(node.values[i].curr);
                    //此处递归
                    insert(node.values[i], target, node.values[i].curr);
                }
            }
        }
    }

    public static void main(String[] args) {
        List<Integer> res = new Solution386_2().lexicalOrder(99);
        System.out.println(res);
    }

}
